package org.kfive.nova.algorithm;

/**
 * Created by admin on 2017-03-19.
 * 数据结构-堆
 */
public class Heap<E extends Comparable> {

    private E heaps[];

    private int size;

    private int limit = 0;

    private int MAX_SIZE = Integer.MAX_VALUE;

    public Heap(){
        this.heaps = (E[])new Object[size];
    }

    public Heap(int size){
        if(size>MAX_SIZE){
            throw new IllegalArgumentException("maxsize exception");
        }
        this.size = size;
    }


    public int add(E element){
        //将新增的值写到数组末尾
        heaps[limit++] = element;
        int j = limit;
        //对堆进行调整
        int p = (limit-1)/2;
        E parent = element;
        while(p>0 && heaps[p]!=null){
            if(heaps[p].compareTo(element)<=0)
                break;
            heaps[j] = heaps[p];
            j = p;
            p = (j-1)/2;
        }
        heaps[j] = element;
        return j;
    }

    private void adjustHeap(){
        int index = 0;
        int lnext = index * 2 + 1;
        E p = heaps[index];
        while (lnext<limit){
            if((lnext+1)<limit && heaps[lnext].compareTo(lnext+1)<0)
                lnext++;
            if(heaps[index].compareTo(heaps[lnext])<=0)
                break;
            heaps[index] = heaps[lnext];
            index = lnext;
            lnext = index * 2 + 1;
        }
        heaps[index] = p;
    }

    public E remove(){
        E removed = heaps[0];
        heaps[0] = heaps[limit];
        heaps[limit] = null;
        limit--;
        adjustHeap();
        return removed;
    }

    public void swim(int index){
        int parent = index/2;
        while(parent>1){
            if(heaps[parent].compareTo(heaps[index])<=0){
                break;
            }
            index = parent;
            parent = index/2;
        }
    }

    public void sink(){

    }
}
